package zuo.algo.c09;

/**
 * 00:05-前缀树
 */
public class TrieTree {

    static class TrieNode {
        char val;
        int pass;
        int end;
        TrieNode[] nextArr;

        TrieNode(char val) {
            this.val = val;
            this.nextArr = new TrieNode[24];
            this.pass = 0;
            this.end = 0;
        }
    }

    static class Trie {
        TrieNode head;

        Trie() {
            this.head = new TrieNode('0');
        }

        public void insert(String str) {
            char[] chars = str.toCharArray();
            TrieNode node = head;
            for (char ch : chars) {
                int idx = ch - 'a';
                if (node.nextArr[idx] == null) {
                    node.nextArr[idx] = new TrieNode(ch);
                }
                node.pass = node.pass + 1;
                node = node.nextArr[idx];
            }
            node.pass = node.pass + 1;
            node.end = node.end + 1;
        }

        public void delete(String str) {
            if (!contain(str)) {
                return;
            }
            TrieNode node = head;
            char[] chars = str.toCharArray();
            for (char ch : chars) {
                node.pass = node.pass - 1;
                int idx = ch - 'a';
                TrieNode next = node.nextArr[idx];
                if (next.pass <= 1) {
                    node.nextArr[idx] = null;
                    return;
                }
                node = next;
            }
            node.pass = node.pass - 1;
            node.end = node.end - 1;
        }

        public boolean contain(String str) {
            char[] chars = str.toCharArray();
            TrieNode node = head;
            for (char ch : chars) {
                int idx = ch - 'a';
                TrieNode next = node.nextArr[idx];
                if (next == null || next.pass <= 0) {
                    return false;
                }
                node = next;
            }
            return node.end > 0;
        }

        public boolean prefix(String str) {
            char[] chars = str.toCharArray();
            TrieNode node = head;
            for (char ch : chars) {
                int idx = ch - 'a';
                TrieNode next = node.nextArr[idx];
                if (next == null || next.pass <= 0) {
                    return false;
                }
                node = next;
            }
            return true;
        }
    }

    public static void main(String[] args) {
        Trie trie = new Trie();
        String[] strArr = {"abc", "abd", "acc", "ada", "abc", "ccc"};
        for (String str : strArr) {
            trie.insert(str);
        }
        System.out.println(trie.contain("ab"));
        System.out.println(trie.contain("aba"));
        System.out.println(trie.contain("abc"));
        System.out.println(trie.prefix("ab"));
        System.out.println(trie.prefix("acc"));
        System.out.println(trie.prefix("acb"));
        trie.delete("abc");
        trie.delete("abc");
        System.out.println(trie.contain("abc"));
    }
}
